package com.liyunhan.GreedyAlgorithm;

/**
 * @Description: 贪心算法
 * 一个n位正整数a, 删去其中的k位, 得到一个新的正整数b,
 * 设计一个贪心算法, 对给定的a和k, 得到最小的b
 * 19990621  4
 * /19990/621
 * @Author: Liyunhan
 * @Date: 2021/12/6 11:11
 */
public class MinNum {
    //算法要求输入n位正整数a和要删去的k位
    private long a;
    private int k;
    //正整数a的位数
    private int n;
    //最小的数b
    private int b;
    //存储输入的n位正整数各位的数组
    private int[] array;

    /**
     * 算法要求必须输入a和k, 故不提供无参构造器
     *
     * @param a
     * @param k
     */
    public MinNum(long a, int k) {
        this.a = a;
        this.k = k;
        //获取输入正整数a的位数并确保只有此处能改变n
        this.n = getDigit();
        //实例化数组
        this.array = new int[n];
        //将正整数的每一位按位存储入数组中
        initArray();
    }

    /**
     * 获取输入正整数a的位数
     *
     * @return
     */
    private int getDigit() {
        long temp = this.getA();
        int count = 0;

        while (temp != 0) {
            temp /= 10;
            count++;
        }
        return count;
    }

    /**
     * 将正整数的每一位按位存储入数组中
     */
    private void initArray() {
        for (int i = n - 1; i >= 0; i--) {
            this.array[i] = (int) (a % 10);
            this.a /= 10;
        }
    }

    /**
     * 实现指数运算
     *
     * @param baseNum
     * @param indexNum
     * @return
     */
    private long myExpCal(int baseNum, int indexNum) {
        long result = 1;
        for (int i = 0; i < indexNum; i++) {
            result *= baseNum;
        }
        return result;
    }

    /**
     * 主算法方法
     * 最小的数字b是n-k位的
     *
     * @return
     */
    public long mainAlgorithm() {
        //首先进行合法性判断(k < n)
        if (k >= n) {
            System.out.println("输入不合法");
            System.exit(-1);
        }
        //"需要选出n-k位数, 删去其他数"
        //第一次选数的小区间位置是[1, k+1]
        //数组索引从0开始
        //minArr用于保存找到的最小值的各位
        int[] minArr = new int[n];
        int startIndex = 0;
        int endIndex = k;
        int tempMin = array[startIndex];
        int tempIndex = startIndex;
        long res = 0;
        for (int i = 0; i < n - k; i++) {
            //循环遍历整个小区间的值, 找出最小值及其索引
            for (int j = startIndex + 1; j <= endIndex; j++) {
                //注意这里一定要用大于, 因为存在位数上数字相同的情况
                if (tempMin > array[j]) {
                    tempIndex = j;
                    tempMin = array[j];
                }
            }
            //最小值写入minArr
            minArr[i] = tempMin;
            //下一次内循环的起始是最小值索引+1, 结束是endIndex+1
            startIndex = tempIndex + 1;
            endIndex++;
            //重新初始化tempMin和tempIndex(如果循环已经结束, 需要提前停止循环, 否则数组越界)
            if (i + 1 >= n - k) break;
            tempMin = array[startIndex];
            tempIndex = startIndex;
        }
        //取出盛放在minArr数组中的最小值
        for (int i = n - k - 1, j = 0; i >= 0; i--, j++) {
            res += minArr[i] * myExpCal(10, j);
        }

        return res;
    }

    public long getA() {
        return a;
    }

    public void setA(long a) {
        this.a = a;
    }

    public int getK() {
        return k;
    }

    public void setK(int k) {
        this.k = k;
    }

    public int getB() {
        return b;
    }

    public void setB(int b) {
        this.b = b;
    }
}
